package Tree.TraversalByLevel;

import Tree.TreeNode;

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;
import java.util.Queue;

/**
 * 二叉树的的层序遍历
 */
public class TraversalByLevel_I {
    public static void main(String[] args) {

    }

    /**
     * 二叉树从上到下层序遍历
     * @param root
     * @return
     */
    public List<List<Integer>> levelOrder(TreeNode root){
        List<List<Integer>> list = new ArrayList<>();
        if(root == null) return list;
        //借助队列实现层序遍历，队列装着每层的节点
        Queue<TreeNode> queue = new LinkedList<>();
        queue.offer(root);
        while(!queue.isEmpty()){
            List<Integer> itemList = new ArrayList<>();
            int len = queue.size();
            while(len > 0){
                TreeNode tmpNode = queue.poll();
                itemList.add(tmpNode.val);
                if(tmpNode.left != null) queue.offer(tmpNode.left);
                if(tmpNode.right != null) queue.offer(tmpNode.right);
                len--;
            }
            list.add(itemList);
        }
        return list;
    }

    /**
     * 二叉树从下到上的层序遍历
     * 与上面相同，最后反转数组即可
     */
    public List<List<Integer>> levelOrderBottom(TreeNode root){
        List<List<Integer>> list = new ArrayList<>();
        if(root == null) return list;
        //借助队列实现层序遍历，队列装着每层的节点
        Queue<TreeNode> queue = new LinkedList<>();
        queue.offer(root);
        while(!queue.isEmpty()){
            List<Integer> itemList = new ArrayList<>();
            int len = queue.size();
            while(len > 0){
                TreeNode tmpNode = queue.poll();
                itemList.add(tmpNode.val);
                if(tmpNode.left != null) queue.offer(tmpNode.left);
                if(tmpNode.right != null) queue.offer(tmpNode.right);
                len--;
            }
            list.add(itemList);
        }
        List<List<Integer>> result = new ArrayList<>();
        for(int i = list.size() - 1; i >= 0; i--){
            result.add(list.get(i));
        }
        return result;
    }
}
